package leetcode_901_1000;

import java.util.Arrays;

public class LeeCode_923 {
    public static void main(String[] args) {
//        System.out.println(threeSumMulti(new int[]{1, 2, 3}, 6));
        System.out.println(threeSumMulti(new int[]{1,0,1,0,2,1,2}, 1));
    }

    private static int threeSumMulti(int[] arr, int target) {
        long mod = (long) (1e9 + 7);
        long[][] dp = new long[4][target + 1];
        for (int k : arr) {
            long[][] tmp = new long[4][target + 1];
            for (int j = 1; j < 4; j++) {
                tmp[j] = Arrays.copyOfRange(dp[j], 0, target + 1);
            }
            if (k > target)
                continue;
            tmp[1][k]++;
            for (int j = k; j <= target; j++) {
                tmp[2][j] += dp[1][j - k];
                tmp[2][j] %= mod;
            }
            tmp[3][target] += dp[2][target - k];
            tmp[3][target] %= mod;
            dp = tmp;
        }
        return (int) dp[3][target];
    }
}